home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / ui / GC / allochblk.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-04-25  |  9.1 KB  |  352 lines
  1. #define DEBUG
  2. #undef DEBUG
  3. #include <stdio.h>
  4. #include "gc.h"
  5. /**/
  6. /* allocate/free routines for heap blocks
  7. /* Note that everything called from outside the garbage collector
  8. /* should be prepared to abort at any point as the result of a signal.
  9. /**/
  10.  
  11. /*
  12.  * Free heap blocks are kept on a list sorted by address.
  13.  * The hb_hdr.hbh_sz field of a free heap block contains the length
  14.  * (in bytes) of the entire block.
  15.  * Neighbors are coalesced.
  16.  */
  17.  
  18. struct hblk *savhbp = (struct hblk *)0;  /* heap block preceding next */
  19.                      /* block to be examined by   */
  20.                      /* allochblk.                */
  21.  
  22. /*
  23.  * Return 1 if there is a heap block sufficient for object size sz,
  24.  * 0 otherwise.  Advance savhbp to point to the block prior to the
  25.  * first such block.
  26.  */
  27. int sufficient_hb(sz)
  28. int sz;
  29. {
  30. register struct hblk *hbp;
  31. struct hblk *prevhbp;
  32. int size_needed, size_avail;
  33. int first_time = 1;
  34.  
  35.     size_needed = WORDS_TO_BYTES(sz>0? sz : -sz);
  36.     size_needed = (size_needed+sizeof(struct hblkhdr)+HBLKSIZE-1) & ~HBLKMASK;
  37. #   ifdef DEBUG
  38.     printf("sufficient_hb: sz = %d, size_needed = 0x%X\n", sz, size_needed);
  39. #   endif
  40.     /* search for a big enough block in free list */
  41.     hbp = savhbp;
  42.     for(;;) {
  43.         prevhbp = hbp;
  44.         hbp = ((prevhbp == (struct hblk *)0)
  45.             ? hblkfreelist
  46.             : prevhbp->hb_next);
  47.  
  48.         if( prevhbp == savhbp && !first_time) {
  49.         /* no sufficiently big blocks on free list */
  50.         return(0);
  51.         }
  52.         first_time = 0;
  53.         if( hbp == (struct hblk *)0 ) continue;
  54.         size_avail = hbp->hb_sz;
  55.         if( size_avail >= size_needed ) {
  56.         savhbp = prevhbp;
  57.         return(1);
  58.         }
  59.     }
  60. }
  61.  
  62. /*
  63.  * Allocate (and return pointer to) a heap block
  64.  *   for objects of size |sz|.
  65.  *
  66.  * NOTE: Caller is responsible for adding it to global hblklist
  67.  *       and for building an object freelist in it.
  68.  *
  69.  * The new block is guaranteed to be cleared if sz > 0.
  70.  */
  71. struct hblk *
  72. allochblk(sz)
  73. long sz;
  74. {
  75.     register struct hblk *thishbp;
  76.     register struct hblk *hbp;
  77.     struct hblk *prevhbp;
  78.     long size_needed,            /* number of bytes in requested objects */
  79.          uninit,                 /* => Found uninitialized block         */
  80.          size_avail;
  81.     int first_time = 1;
  82.  
  83.     char *sbrk();            /* data segment size increasing    */
  84.     char *brk();            /* functions            */
  85.  
  86.     size_needed = WORDS_TO_BYTES(sz>0? sz : -sz);
  87.     size_needed = (size_needed+sizeof(struct hblkhdr)+HBLKSIZE-1) & ~HBLKMASK;
  88. #   ifdef DEBUG
  89.     printf("(allochblk) sz = %x, size_needed = 0x%X\n", sz, size_needed);
  90. #   endif
  91.  
  92.     /* search for a big enough block in free list */
  93.     hbp = savhbp;
  94.     for(;;) {
  95.  
  96.         prevhbp = hbp;
  97.         hbp = ((prevhbp == (struct hblk *)0)
  98.                     ? hblkfreelist
  99.             : prevhbp->hb_next);
  100.  
  101.         if( prevhbp == savhbp && !first_time) {
  102.         /* no sufficiently big blocks on free list, */
  103.         /* let thishbp --> a newly-allocated block, */
  104.         /* free it (to merge into existing block    */
  105.         /* list) and start the search again, this   */
  106.         /* time with guaranteed success.            */
  107.                   int size_to_get = size_needed + hincr * HBLKSIZE;
  108.           extern int holdsigs();
  109.           int Omask;
  110.  
  111.           /* Don't want to deal with signals in the middle of this */
  112.               Omask = holdsigs();
  113.  
  114.                     update_hincr;
  115.             thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );
  116.             heaplim = (char *) (((unsigned)thishbp) + size_to_get);
  117.  
  118.             if( (brk(heaplim)) == ((char *)-1) ) {
  119.                         write(2,"Out of Memory!  Giving up ...\n", 30);
  120.             exit(-1);
  121.             }
  122. #                   ifdef PRINTSTATS
  123.             printf("Need to increase heap size by %d\n",
  124.                    size_to_get);
  125.             fflush(stdout);
  126. #                   endif
  127.             heapsize += size_to_get;
  128.             thishbp->hb_sz = 
  129.             BYTES_TO_WORDS(size_to_get - sizeof(struct hblkhdr));
  130.             freehblk(thishbp);
  131.             /* Reenable signals */
  132.               sigsetmask(Omask);
  133.             hbp = savhbp;
  134.             first_time = 1;
  135.         continue;
  136.         }
  137.  
  138.         first_time = 0;
  139.  
  140.         if( hbp == (struct hblk *)0 ) continue;
  141.  
  142.         size_avail = hbp->hb_sz;
  143.         if( size_avail >= size_needed ) {
  144.         /* found a big enough block       */
  145.         /* let thishbp --> the block      */
  146.         /* set prevhbp, hbp to bracket it */
  147.             thishbp = hbp;
  148.             if( size_avail == size_needed ) {
  149.             hbp = hbp->hb_next;
  150.             uninit = thishbp -> hb_uninit;
  151.             } else {
  152.             uninit = thishbp -> hb_uninit;
  153.             thishbp -> hb_uninit = 1; 
  154.                 /* Just in case we get interrupted by a */
  155.                 /* signal                               */
  156.             hbp = (struct hblk *)
  157.                 (((unsigned)thishbp) + size_needed);
  158.             hbp->hb_uninit = uninit;
  159.             hbp->hb_next = thishbp->hb_next;
  160.             hbp->hb_sz = size_avail - size_needed;
  161.             }
  162.         /* remove *thishbp from hblk freelist */
  163.             if( prevhbp == (struct hblk *)0 ) {
  164.             hblkfreelist = hbp;
  165.             } else {
  166.             prevhbp->hb_next = hbp;
  167.             }
  168.         /* save current list search position */
  169.             savhbp = prevhbp;
  170.         break;
  171.         }
  172.     }
  173.  
  174.     /* set size and mask field of *thishbp correctly */
  175.     thishbp->hb_sz = sz;
  176.     thishbp->hb_mask = -1;  /* may be changed by new_hblk */
  177.  
  178.     /* Clear block if necessary */
  179.     if (uninit && sz > 0) {
  180.         register word * p = &(thishbp -> hb_body[0]);
  181.         register word * plim;
  182.  
  183.         plim = (word *)(((char *)thishbp) + size_needed);
  184.         while (p < plim) {
  185.         *p++ = 0;
  186.         }
  187.     }
  188.     /* Clear mark bits */
  189.     {
  190.         register word *p = (word *)(&(thishbp -> hb_marks[0]));
  191.         register word * plim = (word *)(&(thishbp -> hb_marks[MARK_BITS_SZ]));
  192.         while (p < plim) {
  193.         *p++ = 0;
  194.         }
  195.     }
  196.  
  197. #   ifdef DEBUG
  198.     printf("Returning 0x%X\n", thishbp);
  199.     fflush(stdout);
  200. #   endif
  201.     return( thishbp );
  202. }
  203.  
  204. /* Clear the header information in a previously allocated heap block p */
  205. /* so that it can be coalesced with an initialized heap block.         */
  206. static clear_header(p)
  207. register struct hblk *p;
  208. {
  209.     p -> hb_sz = 0;
  210. #   ifndef HBLK_MAP
  211.       p -> hb_index = (struct hblk **)0;
  212. #   endif
  213.     p -> hb_next = 0;
  214.     p -> hb_mask = 0;
  215. #   if MARK_BITS_SZ <= 60
  216.     /* Since this block was deallocated, only spurious mark      */
  217.     /* bits corresponding to the header could conceivably be set */
  218.     p -> hb_marks[0] = 0;
  219.     p -> hb_marks[1] = 0;
  220. #   else
  221.     --> fix it
  222. #   endif
  223. }
  224.  
  225. /*
  226.  * Free a heap block.
  227.  *
  228.  * Assume the block is not currently on hblklist.
  229.  *
  230.  * Coalesce the block with its neighbors if possible.
  231.  
  232.  * All mark words (except possibly the first) are assumed to be cleared.
  233.  * The body is assumed to be cleared unless hb_uninit is nonzero.
  234.  */
  235. void
  236. freehblk(p)
  237. register struct hblk *p;
  238. {
  239. register struct hblk *hbp, *prevhbp;
  240. register int size;
  241.  
  242.     /* savhbp may become invalid due to coalescing.  Clear it. */
  243.     savhbp = (struct hblk *)0;
  244.  
  245.     size = p->hb_sz;
  246.     if( size < 0 ) size = -size;
  247.     size = 
  248.     ((WORDS_TO_BYTES(size)+sizeof(struct hblkhdr)+HBLKSIZE-1)
  249.          & (~HBLKMASK));
  250.     p->hb_sz = size;
  251.  
  252.     prevhbp = (struct hblk *) 0;
  253.     hbp = hblkfreelist;
  254.  
  255.     while( (hbp != (struct hblk *)0) && (hbp < p) ) {
  256.     prevhbp = hbp;
  257.     hbp = hbp->hb_next;
  258.     }
  259.  
  260.     /* Coalesce with successor, if possible */
  261.       if( (((unsigned)p)+size) == ((unsigned)hbp) ) {
  262.     (p -> hb_uninit) |= (hbp -> hb_uninit);
  263.     p->hb_next = hbp->hb_next;
  264.     p->hb_sz += hbp->hb_sz;
  265.     if (!p -> hb_uninit) clear_header(hbp);
  266.       } else {
  267.     p->hb_next = hbp;
  268.       }
  269.  
  270.     if( prevhbp == (struct hblk *)0 ) {
  271.     hblkfreelist = p;
  272.     } else if( (((unsigned)prevhbp) + prevhbp->hb_hdr.hbh_sz) ==
  273.         ((unsigned)p) ) {
  274.       /* Coalesce with predecessor */
  275.     (prevhbp->hb_uninit) |= (p -> hb_uninit);
  276.     prevhbp->hb_next = p->hb_next;
  277.     prevhbp->hb_sz += p->hb_sz;
  278.     if (!prevhbp -> hb_uninit) clear_header(p);
  279.     } else {
  280.     prevhbp->hb_next = p;
  281.     }
  282. }
  283.  
  284. /* Add a heap block to hblklist or hblkmap.  */
  285. void add_hblklist(hbp)
  286. struct hblk * hbp;
  287. {
  288. # ifdef HBLK_MAP
  289.     long size = hbp->hb_sz;
  290.     long index = divHBLKSZ(((long)hbp) - ((long)heapstart));
  291.     long i;
  292.  
  293.     if( size < 0 ) size = -size;
  294.     size = (divHBLKSZ(WORDS_TO_BYTES(size)+sizeof(struct hblkhdr)+HBLKSIZE-1));
  295.        /* in units of HBLKSIZE */
  296.     hblkmap[index] = HBLK_VALID;
  297.     for (i = 1; i < size; i++) {
  298.     if (i < 0x7f) {
  299.         hblkmap[index+i] = i;
  300.     } else {
  301.         /* May overflow a char.  Store largest possible value */
  302.         hblkmap[index+i] = 0x7e;
  303.     }
  304.     }
  305. # else
  306.     if (last_hblk >= &hblklist[MAXHBLKS]) {
  307.     fprintf(stderr, "Not configured for enough memory\n");
  308.     exit(1);
  309.     }
  310.     *last_hblk = hbp;
  311.     hbp -> hb_index = last_hblk;
  312.     last_hblk++;
  313. # endif
  314. }
  315.  
  316. /* Delete a heap block from hblklist or hblkmap.  */
  317. void del_hblklist(hbp)
  318. struct hblk * hbp;
  319. {
  320. # ifdef HBLK_MAP
  321.     long size = hbp->hb_sz;
  322.     long index = divHBLKSZ(((long)hbp) - ((long)heapstart));
  323.     long i;
  324.  
  325.     if( size < 0 ) size = -size;
  326.     size = (divHBLKSZ(WORDS_TO_BYTES(size)+sizeof(struct hblkhdr)+HBLKSIZE-1));
  327.        /* in units of HBLKSIZE */
  328.     for (i = 0; i < size; i++) {
  329.     hblkmap[index+i] = HBLK_INVALID;
  330.     }
  331. # else
  332.     register struct hblk ** list_entry;
  333.     last_hblk--;
  334.     /* Let **last_hblk use the slot previously occupied by *hbp */
  335.     list_entry = hbp -> hb_index;
  336.     (*last_hblk) -> hb_index = list_entry;
  337.     *list_entry = *last_hblk;
  338. # endif
  339. }
  340.  
  341. /* Initialize hblklist */
  342. void init_hblklist()
  343. {
  344. #   ifdef DEBUG
  345.     printf("Here we are in init_hblklist - ");
  346.     printf("last_hblk = %x\n",&(hblklist[0]));
  347. #   endif
  348. #   ifndef HBLK_MAP
  349.       last_hblk = &(hblklist[0]);
  350. #   endif
  351. }
  352.